最后一遍-L33-Search in Rotated Sorted Array
LeetCode 33. Search in Rotated Sorted Array
从根本上面说，这个数据很有意思，只是正常的数据进行的一次转换，我们需要的就是怎么转换回来，或者说在经典的算法中，下标计算的时候，怎么能够不受这次转换的影响。
描述：
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
Your algorithm's runtime complexity must be in the order of O(log n).
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
思路：
既然是有一段数据被翻转回到了数据的开头，那我们怎么能够比较巧妙的翻转回去尼？
i = (i + k) % n
具体的代码如下：
public class L33 {
public static void main(String[] args) {
System.out.println("Keep Happy !");
// System.out.println(search(new int[]{4,5,6,7,0,1,2},3));
System.out.println(search(new int[]{4,5,6,7,0,1,2},0));
System.out.println(search(new int[]{1,3,5},5));
}
public static int search(int a[], int target){
if(null == a || a.length == 0) return -1;
if(a.length == 1) return a[0]==target?0:-1;
int n = a.length;int turn=n-1;
//寻找转折点，方法①
for (; turn >0 && a[turn] > a[turn-1]; turn--);
//寻找转折点，方法②
int start = 0; int end = n-1;
while(start < end){
int mid = start+ (end-start)/2;
if(a[mid] > a[end]){
start=mid+1;
}else{
end = mid;
}
}
turn=end;
int from =turn; int to = turn+a.length;
while(from <= to){
int mid = (from+to)/2;
if(a[mid%n] > target){
to = mid-1;
} else if (a[mid%n] < target) {
from=mid+1;
}else {
return mid%n;
}
}
return -1;
}
}